package 滑动窗口;

/**
 给你一个字符串 s，找到 s 中最长的回文子串。
 输入：s = 'babad'
 输出：'bab'
 解释：'aba' 同样是符合题意的答案。
 输入：s = 'cbbd'
 输出：'bb'
 输入：s = 'a'
 输出：'a'
 */
public class LeetCodeDemo5 {
    public static void main(String[] args) {
        String s = "babad";
        int len = s.length();
        if (len<2){
            System.out.println(s);
        }
        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();
        // 枚举所有长度大于l的字串
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        System.out.println(s.substring(begin, begin + maxLen));
    }

    private static boolean validPalindromic(char[] charArray, int left, int right) {
        while (left < right){
            if (charArray[left] != charArray[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}
